//
// Created by ASUS on 2024/7/22/星期一.
//
/*
 * 给你一个长度为 n 的整数数组 nums ，n 是 偶数 ，同时给你一个整数 k 。
你可以对数组进行一些操作。每次操作中，你可以将数组中 任一 元素替换为 0 到 k 之间的 任一 整数。
执行完所有操作以后，你需要确保最后得到的数组满足以下条件：
存在一个整数 X ，满足对于所有的 (0 <= i < n) 都有 abs(a[i] - a[n - i - 1]) = X 。
请你返回满足以上条件 最少 修改次数。
示例 1：
输入：nums = [1,0,1,2,4,3], k = 4
输出：2
解释：
我们可以执行以下操作：
将 nums[1] 变为 2 ，结果数组为 nums = [1,2,1,2,4,3] 。
将 nums[3] 变为 3 ，结果数组为 nums = [1,2,1,3,4,3] 。
整数 X 为 2 。
示例 2：
输入：nums = [0,1,2,3,3,6,5,4], k = 6
输出：2
解释：
我们可以执行以下操作：
将 nums[3] 变为 0 ，结果数组为 nums = [0,1,2,0,3,6,5,4] 。
将 nums[4] 变为 4 ，结果数组为 nums = [0,1,2,0,4,6,5,4] 。
整数 X 为 4 。
提示：
2 <= n == nums.length <= 105
n 是偶数。
0 <= nums[i] <= k <= 105
 */
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
	int minChanges(vector<int>& nums, int k) {
		int n=nums.size();
		vector<int> d(k+2);
		for(int i=0;i<n/2;i++){
			int p=nums[i],q=nums[n-1-i];
			if(p>q) swap(p,q);
			int x=q-p;
			int mx=max(q,k-p);
			//X∈[0,q-p-1]修改1次，X=q-p不需要修改
			d[0]++;
			d[x]--;
			//X∈[q-p+1,mx]修改1次
			d[x+1]++;
			d[mx+1]--;
			//X∈[mx+1,k]修改2次
			d[mx+1]+=2;
		}
		partial_sum(d.begin(),d.end(),d.begin());
		return ranges::min(d);
	}
};
